﻿#include <iostream>
#include <string>
#include <vector>
#include <cctype>

using namespace std;

// --------------------------
// 全局变量
// --------------------------
vector<string> tokens;  // 存储分词后的 token
int pos = 0;            // 当前读取位置（索引）
bool debug = true;      // 是否显示匹配过程

// --------------------------
// 辅助函数：匹配终结符
// --------------------------
bool match(const string& expected) {
    if (pos < tokens.size() && tokens[pos] == expected) {
        if (debug) cout << "Matched: " << expected << endl;
        pos++;
        return true;
    }
    return false;
}

// --------------------------
// 语法分析函数声明
// --------------------------
bool E();   // E → T E'
bool E_();  // E' → + T E' | ε
bool T();   // T → F T'
bool T_();  // T' → * F T' | ε
bool F();   // F → ( E ) | id

// --------------------------
// 语法分析函数定义
// --------------------------

// E → T E'
bool E() {
    if (debug) cout << "Enter E" << endl;
    return T() && E_();
}

// E' → + T E' | ε
bool E_() {
    if (debug) cout << "Enter E'" << endl;
    if (pos < tokens.size() && tokens[pos] == "+") {
        match("+");
        return T() && E_();
    }
    return true; // E' → ε
}

// T → F T'
bool T() {
    if (debug) cout << "Enter T" << endl;
    return F() && T_();
}

// T' → * F T' | ε
bool T_() {
    if (debug) cout << "Enter T'" << endl;
    if (pos < tokens.size() && tokens[pos] == "*") {
        match("*");
        return F() && T_();
    }
    return true; // T' → ε
}

// F → ( E ) | id
bool F() {
    if (debug) cout << "Enter F" << endl;
    if (pos < tokens.size()) {
        if (tokens[pos] == "id") {
            return match("id");
        }
        else if (tokens[pos] == "(") {
            match("(");
            if (E() && match(")")) {
                return true;
            }
        }
    }
    return false;
}

// --------------------------
// 输入分词处理函数
// --------------------------
vector<string> tokenize(const string& input) {
    vector<string> result;
    string token;
    for (char ch : input) {
        if (isspace(ch)) {
            if (!token.empty()) {
                result.push_back(token);
                token.clear();
            }
        }
        else if (ch == '+' || ch == '*' || ch == '(' || ch == ')') {
            if (!token.empty()) {
                result.push_back(token);
                token.clear();
            }
            result.push_back(string(1, ch));
        }
        else {
            token += ch;
        }
    }
    if (!token.empty()) result.push_back(token);
    result.push_back("#"); // 结束符
    return result;
}

// --------------------------
// 主语法分析入口
// --------------------------
void parse(const string& input) {
    tokens = tokenize(input);
    pos = 0;

    cout << "Token序列: ";
    for (const auto& tok : tokens) {
        cout << tok << " ";
    }
    cout << endl;

    bool result = E();
    if (result && tokens[pos] == "#") {
        cout << "\n✅ 该符号串是该文法的句子。" << endl;
    }
    else {
        cout << "\n❌ 该符号串不是该文法的句子。" << endl;
    }
}

// --------------------------
// 主函数：用户输入
// --------------------------
int main() {
    string input;
    cout << "请输入符号串（如 id + id * id 或 ( id + id ) * id）：" << endl;
    getline(cin, input);

    parse(input);
    return 0;
}
